//归并排序(2路归并)【外部排序就是特殊的归并排序】
/*
    2路归并树形态上就是一棵倒立的二叉树
*/
/*
    稳定
    时间复杂度O(nlogn)【n个元素进行2路归并排序，归并趟数为⌈logn⌉，且每趟归并时间复杂度为O(n),则算法时间复杂度为O(nlogn)】;
    最好空间复杂度O(n)【来自于辅助数组B】;
*/

#include <iostream>

using namespace std;

int B[100] = {0};   //辅助数组B

//A[low……mid]和A[mid+1……high]各自有序，将两个部分合并【即将两个有序序列合并为一个大的有序序列。这里是2路归并，也可以是多路归并(可以使用"败者树"的数据结构来优化多路平衡归并)】
void Merge(int A[], int low, int mid, int high)
{
    int i, j, k;
    for (k = low; k <= high; k++)   //将A中所有元素复制到B中(这里的A可能是划分后的子表)
        B[k] = A[k];
    for (i = low, j = mid+1, k = i; i <= mid && j <= high; k++) //合并数组B的左右两部分(i和j分别是两部分的指针)并重新赋值返还给A
    {
        //将两部分的较小值复制到A中
        if (B[i] <= B[j])
            A[k] = B[i++];
        else
            A[k] = B[j++];
    }
    while (i <= mid)    //若B的右子表元素用完了，则把左子表元素复制到A未被复制的区域
        A[k++] = B[i++];
    while (j <= high)   //若B的左子表元素用完了，则把右子表元素复制到A未被复制的区域
        A[k++] = B[j++];
    return;
}

//归并排序
void MergeSort(int A[], int low, int high)  //递归实现，可对比二叉树的后序遍历(左右根)【先合并再处理(合并)父结点(即合并后的有序子序列)】
{
    if (low < high) //递归跳出条件
    {
        int mid = (low + high) / 2; //把表A"从中间划分"为左右两部分
        MergeSort(A, low, mid);     //【左】对左子表递归归并排序
        MergeSort(A, mid+1, high);  //【右】对右子表递归归并排序
        Merge(A, low, mid, high);   //【根】"合并"操作
    }
    return;
}


//测试代码
int main()
{
    int A[100] = {2, 4, 3, 7, 9, 1, 6, 5, 8};
    MergeSort(A, 0, 8);
    for (int i = 0; i < 9; ++i)
        cout << A[i] << ' ';
    return 0;
}